The invention relates generally to computer systems, and deals more particularly with sharing of processing time of one or more processors by multiple users.
Often in a computer system, many programs or users require execution concurrently. There may be one or more processors available to execute the multiple programs. Any one processor can only execute one program or transaction at any one time. If two or more programs request execution at the same time, and there is only one processor or fewer processors than the number of programs requiring execution, the operating system must determine which program can use the one or each processor at any one time. Typically this decision is based on a relative priority of each of the programs. Typically also, programs which are in a wait state, such as those waiting for a slow I/O operation to complete, are xe2x80x9csuspendedxe2x80x9d and therefore not eligible to compete for the processor regardless of their priority.
In addition to deciding which program can utilize the one or each processor at a particular time, the operating system must also determine how long the selected program can utilize the respective processor after it begins to execute so that other programs of equal (or perhaps lower) priority can get their turn. There are several known techniques for determining how long each program should be permitted to utilize a processor after it begins to execute. In the simplest technique, the highest priority program maintains its use of the processor until completion (or suspension). However, this may permit this program to xe2x80x9chogxe2x80x9d the processor, and xe2x80x9cstarvexe2x80x9d the other programs. In another known technique, each program which is selected for execution is given a share or xe2x80x9cslicexe2x80x9d of the total processor time. The shares of the programs can be equal or preferably weighted based on various factors. One known technique to weight the shares is as follows. Some of programs are defined to command an xe2x80x9cabsolutexe2x80x9d or definite share of the total processor time, and others are defined to command a xe2x80x9crelativexe2x80x9d share of the remaining processor time. The absolute shares are xe2x80x9ctaken off the topxe2x80x9d and the relative shares divide the remainder in proportion to their relative shares. For example, a first program is defined with a forty percent absolute share, a second program is defined with a one hundred relative share and a third program is defined with a three hundred relative share. In this scenario, the first program will command forty percent of the total processor time, the second program will command fifteen percent of the total processor time and the third program will command forty five percent of the total processor time.
A program may not need its entire absolute or relative share. A known technique to allocate the excess in this absolute/relative share environment is to give all the excess to the program with the highest absolute or relative share. If the excess were a small percentage of the total processor time, this known technique would suffice. However, in many cases, the excess is substantial, such as one half of the total processor time, and it may not be optimum to allocate all the excess to one program.
Accordingly, a general object of the present invention is to provide an improved system for allocating excess processor time to multiple programs or users.
The present invention resides in a computer system for allocating processor time to multiple users. A systems operator or a user specifies to the computer a share of processor time for each user. The share can be absolute or relative. The system executes users which are I/O bound with processor time less than their respective, specified share(s) by not using significant processor time on users which are waiting for an I/O operation to complete but expediting allocation of a processor to users after their respective I/O operations complete. The system executes users which are CPU bound with processor time greater than their respective, specified share(s) based on their respective shares in relation to a sum of shares of other CPU bound users but excluding shares of I/O bound users.
In accordance with another feature of the present invention, for each user there is also a specified xe2x80x9csoft limitxe2x80x9d, xe2x80x9chard limitxe2x80x9d or xe2x80x9cno limitxe2x80x9d. When any hard limit user reaches its hard limit, no further allocation is made. When any soft limit user reaches its soft limit, no further allocation is made to this soft limit user if any other soft limit user has yet to reach its soft limit or any other hard limit user has yet to reach its hard limit or if there are any unlimited users. The other soft limit and hard limit users who have not yet reached their limits continue to receive extra shares until they also reach their respective limits. When all other soft limit users have reached their soft limits and all hard limit users have reached their hard limits and if there are no unlimited users, then the soft limit user with the greatest absolute share or relative share (computed as if there was no unused processing time) receives all the remaining unused processing time.
The share allocation technique of the present invention is implemented by re-positioning or offsetting each user downward in the dispatch list after the user completes each time slice. The amount of offset for a user is based on the magnitude of the absolute or relative share of the user and the current position of the user. After completing each time slice for a user located in a bottom part of the dispatch list, the user is repositioned later in the dispatch list by an offset based on a magnitude of the user""s share in relation to the shares of other users located in the bottom part of the dispatch list. However, after completing each time slice for a user located in a top part of the dispatch list, the user is repositioned later in the dispatch list by an offset based on the magnitude of the user""s share in relation to other users throughout the dispatch list.
The soft and hard users are limited in accordance with their specified limits by establishing a significant, minimum offset when they reach their limits. Moreover, the hard limited users are taken off a run list when they exceed their limits.